/*
 *
 * This program is free software; you can redistribute it and/or modify 
 * it under the terms of the GNU General Public License version 2 as 
 * published by the Free Software Foundation.
 *
 * seq_list.h is for what ...
 *
 * Version: ***: seq_list.h  Mon Sep 19 21:57:27 2011 poponion Exp $
 *
 * Authors:
 *   Author poponion <huangcm85@gmail.com>
 *     -some work detail if you want 
 *
 */

#ifndef SEQ_LIST_H_
#define SEQ_LIST_H_

#include "common/my_define.h"
#include "common/my_log.h"
namespace poponion{
  namespace datastruct{
    using namespace poponion::common;
    template<class T>
    struct Node
    {
      T data_;
    };

    //线性表的顺序实现
    template<class T>
    class SeqList
    {
    private:
      Node<T>* head_;         //head of list
      int32_t length_;        //node num of list
      int32_t capacity_;      //capacity of list
      int32_t inc_rate_;   
    public:
    SeqList():head_(NULL), length_(0), capacity_(0), inc_rate_(2)
      {
      }
     
      /**
       * Init a SeqList, alloc memory for capacity node
       * 
       * @param capacity  capacity of this list
       * @param inc_rate  incrate when list is full
       * @return int      return MY_SUCCESS if init successful else return MY_ERROR
       */
      int init(int32_t capacity = 100, int32_t inc_rate = 2)
      {
        int ret = MY_SUCCESS;
        if (capacity <= 0 || inc_rate <= 1)
        {
          MY_LOG_WARN("Invalid argument capacity=%d inc_rate=%d",
                      capacity, inc_rate);
          ret = MY_ERROR;
        }
        else
        {
          capacity_ = capacity;
          inc_rate_ = inc_rate;
          head_ = reinterpret_cast<Node<T>* >(malloc(capacity_ * sizeof(Node<T>)));
          if (NULL == head_)
          {
            MY_LOG_ERROR("Alloc memory failed");
            ret = MY_ERROR;
          }
        }
        return ret;
      }
      
      /**
       * Destroy the list, free memory reset members
       */
      void destroy()
      {
        if (NULL != head_)
        {
          free(head_);
          head_ = NULL;
        }
        capacity_ = 0;
        length_   = 0;
      }
      
      /**
       * Delete all node in list, do not free memory
       */
      void clear()
      {
        length_ = 0;
      }
      
      /**
       * Insert a node into the list
       * @param data  node to insert
       * @return int  return MY_SUCCESS if insert done, else return MY_ERROR
       */
      int insert(const T& data)
      {
        int ret = MY_SUCCESS;
        Node<T> node;
        node.data_ = data;
        
        //check list is full
        if (capacity_ == length_)
        {
          ret = enlargeList();
        }
        if (MY_SUCCESS == ret)
        {
          *(head_ + length_) = node;
          ++length_;
        }
        return ret;
      }
      
      /**
       * Delete one node
       * @param data  Node to delete
       * @return int  return MY_SUCCESS if delete done, else return MY_ERROR
       */
      int deleteNode(const T& data)
      {
        int ret = MY_SUCCESS;
        int offset = findNode(data);
        if (-1 == offset)
        {
          MY_LOG_ERROR("data not exist in list");
        }
        else
        {
          //  memcpy(head_+offset+1
        }
        return ret;
      }

      
      /**
       * Find the offset of the node
       * @param data  Node to find
       * @return int  Offset of the node, return -1 if not exist
       */
      int findNode(T data)
      {
        int offset = -1;
        for(int index = 0; index < length_; ++index)
        {
          if (*(head_ + index).data_ == data)
          {
            offset = index;
            break;
          }
        }
        return offset;
      }

      int enlargeList()
      {
        int ret = MY_SUCCESS;
        Node<T>* tmp = reinterpret_cast<Node<T>*>(malloc(sizeof(Node<T>) * capacity_ * inc_rate_));
        if (NULL == tmp)
        {
          MY_LOG_ERROR("Alloc memory failed");
          ret = MY_ERROR;
        }
        if (MY_SUCCESS == ret)
        {
          capacity_ = capacity_ * inc_rate_;
          memcpy(tmp, head_, sizeof(Node<T>) * capacity_);
          free(head_);
          head_ = tmp;
        }
        return ret;
      }

      int32_t length()
      {
        return length_;
      }

      int32_t capacity()
      {
        return capacity_;
      }
    };
  }
}
#endif
